emscripten
Downloading...

Resize canvas Lock/hide mouse pointer    


/ >> augmented_containers >> augmented_graph_t
jhcarl0814.github.io
	Augmented Containers
		Sequence
			augmented_*****_t
			augmented_deque_t
			augmented_sequence_t
		Associative
			augmented_***​/​***​/​********​/​********_t (has-a augmented_sequence_t)
		Graph

augmented_containers::augmented_graph_t

#include<augmented_containers/augmented_graph.hpp> (one single header file library)
enum class augmented_graph_part_data_structure_e {
	top_tree,
	link_cut_tree,
	a_new_approach_to_dynamic_all_pairs_shortest_paths,
	fully_dynamic_planarity_testing_in_polylogarithmic_time, };
template<
	typename vertex_t,
	typename edge_t,
	typename parts_data_structure_and_parameters_t,
	std::strict_weak_order<vertex_t, vertex_t> compartor_vertex_t = std::less<vertex_t>,
	std::strict_weak_order<edge_t, edge_t> compartor_edge_t = std::less<edge_t>,
	typename allocator_vertex_t = std::allocator<vertex_t>
> struct augmented_graph_t;

augmented_graph_t is an augmented, general-purpose graph. It's part of the augmented containers library, providing a more powerful version of containers (let containers (and possibly its subranges) always have several accompanying results of algorithms/views), as well as <algorithm> and <ranges> (when the input changes, refresh output values/ranges in logarithmic time complexity). To help understand what kind of problems the library solves: Dynamic problem (algorithms) - Wikipedia, Augmented map - Wikipedia.

Examples

empty

Each vertex_t/edge_t(std::monostate) does not store any information. No parts are attached to the graph. Only structual information of the graph is maintained.

augmented_containers::augmented_graph_t<
	std::monostate,
	std::monostate,
	std::tuple<>,
	monostate_comparator_t,
	monostate_comparator_t
> augmented_graph;

arbitrary_spanning_forest

A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t(void) does not store any information. The internal operation does not suggest any tree edge to cut when inserted edge's 2 vertices belong to same tree. An arbitrary spanning forest of the graph is maintained, so circuit rank (cyclomatic number), a cycle basis and a feedback edge set of the graph can be answered quickly. Connected components of the graph and whether 2 vertices belong to same component can also be answered quickly, but note that there are faster data structures dedicated to maintaining connectivity information of graphs.

augmented_containers::augmented_graph_t<
    std::monostate,
    std::monostate,
    std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_empty_t<>>
    >,
    monostate_comparator_t,
    monostate_comparator_t
> augmented_graph;

minimum_spanning_forest

Each edge_t(int) stores the weight of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t(graph_t::it_edge_it_vertex_t) points to the maximum-weight edge among the cluster's path descendant edges.

When inserting an edge whose 2 vertices belong to same tree, augmented_graph_part_data_structure_e::top_tree exposes the 2 vertices (so the iterator pointing to the maximum-weight edge among the tree path's edges can be read from root cluster). get_top_tree_internal_operations_selecting_path_t selects the old edge for augmented_graph_part_data_structure_e::top_tree to cut before linking the new edge, or doesn't select any edge and augmented_graph_part_data_structure_e::top_tree just put the edge to the set of edges that do not belong to the forest.

get_top_tree_internal_operations_selecting_path_t let augmented_graph_part_data_structure_e::top_tree order the set of edges that do not belong to the forest in weight-increasing order, so that when eraseing a tree edge, augmented_graph_part_data_structure_e::top_tree look for replacement among the edges in weight-increasing order.

augmented_containers::augmented_graph_t<
	std::monostate,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_selecting_path_t<std::less<void>>>
	>,
	monostate_comparator_t
> augmented_graph;

minimum_spanning_forests

Two augmented_graph_part_data_structure_e::top_trees are attached to the graph. Part-0 and part-1 maintain minimum spanning forest and maximum spanning forest of the graph respectively. Negating the comparator of minimum spanning forest configuration results in maximum spanning forest configuration.

augmented_containers::augmented_graph_t<
	std::monostate,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_selecting_path_t<std::less<void>>>,
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_selecting_path_t<std::greater<void>>>
	>,
	monostate_comparator_t
> augmented_graph;

tree_nearest_marked_vertexes

Each vertex_t(bool) stores whether the vertex is marked. Each edge_t(int) stores the length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores: tree path length between its 2 boundary vertices, the nearest marked vertices (among the cluster's descendant edges' vertices excluding the 2 boundary vertices) and distance to them for each its 2 boundary vertices. Quickly answers the nearest marked vertices to any vertex and its distance to them by exposeing the vertex and adding the information excluded. Quickly mark/unmark any vertex by exposeing the vertex (so that no cluster_t has the vertex as non-boundary descendant vertex) and updateing it. Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).

augmented_containers::augmented_graph_t<
	bool,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_nearest_marked_vertices_t<int>>
	>
> augmented_graph;

tree_diameter_and_centers

Each edge_t(int) stores the non-negative length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores: tree path length between its 2 boundary vertices, eccentricity and 1 farthest vertex (through the cluster's descendant edges) for each its 2 boundary vertices, diameter and 2 farthest vertices (through the cluster's descendant edges). Quickly answers the eccentricity and 1 farthest vertex of any vertex by exposeing the vertex. Quickly answers the diameter and 2 farthest vertices of the graph because the information is stored in root cluster. Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).

augmented_containers::augmented_graph_t<
	std::monostate,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_diameter_t<int>>
	>,
	monostate_comparator_t
> augmented_graph;

tree_medians

Each vertex_t(int) stores the non-negative weight of the vertex. Each edge_t(int) stores the non-negative length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores: tree path length between its 2 boundary vertices, distance-weighted weight sum of vertices (among the cluster's descendant edges' vertices excluding the 2 boundary vertices) for each its 2 boundary vertices, weight sum of vertices (among the cluster's descendant edges' vertices excluding the 2 boundary vertices). Quickly answers the median of the graph by non_local_searching choosing sub-cluster having larger weight sum of vertices (including its 2 boundary vertices) each round, exposeing the 2 vertices of the result edge and adding the information excluded. Quickly change the weight of any vertex by exposeing the vertex (so that no cluster_t has the vertex as non-boundary descendant vertex) and updateing it. Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).

augmented_containers::augmented_graph_t<
	int,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_median_t<int>>
	>
> augmented_graph;

tree_jump_and_meet

Each edge_t(int) stores the positive length of the edge. A augmented_graph_part_data_structure_e::top_tree is attached to the graph. Each cluster_t stores tree path length between its 2 boundary vertices. Quickly answers: along the tree path between any 2 vertices, edge including any number (each edge includes range [0,l1), [l1,l1+l2), ..., or each edge includes range (0,l1], (l1,l1+l2], ...) starting from one of the vertex, by exposing the 2 vertices and searching among path descendant sub-clusters between the 2 vertices. Quickly answers the intersection vertex of any 3 vertices by exposing each of 3 vertex pairs and reading tree path length between each vertex pair from the root cluster, along the tree path between v1 and v2 calculating the 2 edges including number (d12+d13-d23)/2 using left-inclusive-right-exclusive view and left-exclusive-right-inclusive view respectively (the intersection vertex is the common vertex of the 2 edges). Quickly change the length of any edge by updateing it (the underlying top tree performs a cut and a link).

augmented_containers::augmented_graph_t<
	std::monostate,
	int,
	std::tuple<
		std::pair<std::integral_constant<augmented_containers::augmented_graph_part_data_structure_e, augmented_containers::augmented_graph_part_data_structure_e::top_tree>, augmented_containers::augmented_graph_helpers::get_top_tree_internal_operations_distance_t<int>>
	>,
	monostate_comparator_t
> augmented_graph;